package 代码随想录_动态规划.完全背包;

/**完全背包问题
 * 给定 n 种物品, 每种物品都有无限个. 第 i 个物品的体积为 A[i], 价值为 V[i].
 * 再给定一个容量为 m 的背包.问可以装入背包的最大价值是多少?
 * 完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。*******************
 * @author zx
 * @create 2022-05-24 17:02
 * 1.确定dp数组（dp table）以及下标的含义
 *
 * 2.确定递推公式
 *
 * 3.dp数组如何初始化
 *
 * 4.确定遍历顺序
 *  完全背包的物品是可以添加多次的，所以要从小到大去遍历
 * 5.举例推导dp数组
 *
 * 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！
 * 默认 遍历物品在外层，遍历背包容量在内层
 */
public class lintcode440_背包问题三 {
    public int backPackIII(int[] a, int[] v,int m) {
        //dp[i]:容量为i的背包,装入的最大物品价值为dp[i]
        int[] dp = new int[m + 1];
        dp[0] = 0;
        for(int i = 0;i < a.length;i++){//遍历物品
            for(int j = a[i];j <= m;j++){//遍历背包
                dp[j] = Math.max(dp[j],dp[j - a[i]] + v[i]);
            }
        }
        return dp[m];
    }
}
